Критерий полуэйлерова графа

Граф является **полуэйлеровым** (без изолированных вершин) $\iff$ он связен и все вершины (кроме, возможно, двух) имеют четную степень.

$\Large{\implies}$ Пусть в графе $G$ есть эйлеров путь из $u$ в $v$. Очевидно, что граф связен. Степень каждой промежуточной вершины четна, так как для каждого входящего ребра есть выходящее. Если $u = v$ (эйлеров цикл), то и степень $u$ четна, и в графе 0 вершин нечетной степени. Если $u \neq v$, то степени $u$ и $v$ нечетны, а все остальные — четны, и в графе 2 вершины нечетной степени. $\Large{\impliedby}$ Пусть граф $G$ связен. Число вершин нечетной степени может быть только 0 или 2. Если в графе 0 вершин нечетной степени, то по критерию эйлерова графа в $G$ есть эйлеров цикл, а значит, и эйлеров путь. Если в графе 2 вершины нечетной степени (пусть это $u$ и $w$), добавим к графу $G$ новую вершину $v$ и ребра $(v, u)$, $(v, w)$. В полученном графе $G'$ все вершины будут иметь четную степень, и он останется связным. Следовательно, в $G'$ существует эйлеров цикл. Удаление из этого цикла вершины $v$ и инцидентных ей ребер дает эйлеров путь в исходном графе $G$ из $u$ в $w$. $\square$